#include"Tree.h"
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)//后序遍历
{
    if(root==NULL)
    {
        return;
    }


    BinaryTreeDestory(&(*root)->left);
    BinaryTreeDestory(&(*root)->right);
    free(*root);

}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
    if(root==NULL)
        return 0;

    return 1+BinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);//前序遍历

}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
    if(root==NULL)
        return 1;
return BinaryTreeLeafSize(root->left)+BinaryTreeLeafSize(root->right);

}

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
    if(root==NULL)
    return 0;
    if(k==1)
    return 1;

    return BinaryTreeLevelKSize(root->left,k-1)+BinaryTreeLevelKSize(root->right,k-1);
}

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
   if(root==NULL)
     return NULL;
   if(root->data==x)
       return root;


    BTNode* left= BinaryTreeFind(root->left,x);
    if(left)
    {
        return left;
    }
     return BinaryTreeFind(root->right,x);

}
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{
    if(root)
    {
        printf("%c",root->data);
        BinaryTreePrevOrder(root->left);
        BinaryTreePrevOrder(root->right );
    }
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
    if(root)
    {

        BinaryTreePrevOrder(root->left);
        printf("%c",root->data);
        BinaryTreePrevOrder(root->right );
    }
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
    if(root)
    {
        BinaryTreePrevOrder(root->left);
        BinaryTreePrevOrder(root->right );
        printf("%c",root->data);
    }
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)//基于队列
{
       Queue tier;
       QueueInit(&tier);//初始化队列
       if(root!=NULL)
       {
           QueuePush(&tier,root);//先入头节点
       }


       while(!QueueEmpty(&tier))//判断队列是不是为空
       {
           BTNode *Front=QueueFront(&tier);//取队头元素节点的指针，这个是关键,没有她就不知道如何访问每个节点的左右子树
           printf("%c ",Front->data);//取栈顶元素
           QueuePop(&tier);//队头出队列
           if(Front->left!=NULL)
           {
               QueuePush(&tier,Front->left);//出队列的时候吧左右节点都带上
           }
           if(Front->right!=NULL)
           {
               QueuePush(&tier,Front->right);
           }
       }
    QueueDestory(&tier);//销毁队列
}
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)//基于队列
{
    Queue tier;
    QueueInit(&tier);//初始化队列

    if(root!=NULL)
    {
        QueuePush(&tier,root);//先入头节点
    }
    while(!QueueEmpty(&tier))//判断队列是不是为空
    {
        BTNode *Front = QueueFront(&tier);//取队头元素节点的指针，这个是关键,没有她就不知道如何访问每个节点的左右子树
        QueuePop(&tier);//队头出队列
       if(Front==NULL)
       {
           break;
       }

            QueuePush(&tier,Front->left);//出队列的时候吧左右节点都带上
            QueuePush(&tier,Front->right);
    }

    while(!QueueEmpty(&tier))
    {
        BTNode *Front = QueueFront(&tier);//取队头元素节点的指针，这个是关键,没有她就不知道如何访问每个节点的左右子树
        if(Front!=NULL)
        {
            return false;
        }
        QueuePop(&tier);//队头出队列

    }
    return true;
}
